به نام خدا
Title: Low Complexity Routing Algorithm for Rearrangeable Switching Networks
Authors: Amitabha Chakrabarty Martin Collier
Abstract: Rearrangeable switching networks have been a topicof interest for a long time among the research community.Routing algorithms for this class of networks have attractedlots of researchers along with other related areas, such asmodiï¬?cation of the networks structure, crosspoints reduction etc.In this paper a new routing algorithm is presented for symmetricrearrangeable networks built with 2 × 2 switching element. Anew matrix based abstraction model is derived to determineconflict free routing paths for each input-output request. Eachstage of a network is mapped into a set of sub-matrices andnumber of matrices in each stage correspond to number ofsubnetworks in that stage. Once the input permutation is given,matrix cells are populated with binary values depending onthe position of the switching elements in the actual hardwareand their mapped matrix cells. These binary values control therouting decision in the underlying hardware. This new routingalgorithm is capable of connection setup for partial permutation,m = Ï?N , where N is the total input numbers and m is thenumber of active inputs. Overall the serial time complexity ofthis method is O(N logN)1 and O(mlogN) where all N inputsare active and with m < N active inputs respectively. Thetime complexity of this routing algorithm in a parallel machinewith N completely connected processors is O(log2N). With mactive requests the time complexity goes down to O(logmlogN),which is better than the O(log2m + logN), reported in theliterature for 212[(log2Nâˆ_4logN)12âˆ_logN ] ≤ Ï? ≤ 1. Later half ofthis paper demonstrates how this routing algorithm is applicablefor crosstalk free routing in optical domain.
Publish Year: 2013
Publisher: AINA - IEEE
Number of Pages: 8
موضوع: الگوریتم مسیر یابی، شبکه های کامپیوتری
ایران سای – مرجع مقالات علمی فنی مهندسی
حامی دانش بومی ایرانیان
